package com.xw.util;


/**
 * @author XW
 * @data 2023/8/3 13:43
 * @description 生成随机的二叉树
 */
public class GenerateBinaryTreeUtils {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    /**
     *  生成二叉树
     * @param maxLevel 最大深度
     * @param maxValue 最大值
     * @return
     */
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }
    
    private static Node generate(int level, int maxLevel, int maxValue) {
        
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    /**
     * @param head      传入的节点
     * @param height　　层数(根节点为0)
     * @param to       表示的特定节点  H表示根节点   ^表示父亲节点在左上方　v表示父亲节点在左下方
     * @param len　　　 指定每一个节点打印的宽度(总宽度)
     */
    public static void printTree(Node head,int height,String to,int len){
        if(head == null) {
            return;
        }
        // 递归右子树
        printTree(head.right,height + 1,"v",len);
        // 加上两边指示的字符
        String val = to + head.value + to;
        int lenV = val.length();
        //  左边的空格  ((总长度-值所占长度)，然后分一半)
        int lenL = (len - lenV)/2;
        //  右边的空格  (总-值-左边空格长度)
        int lenR = len - lenV - lenL;
        // len*length是对应的层数对应的空格
        System.out.println( getSpace(len * height) + getSpace(lenL) + val + getSpace(lenR));
        // 递归左子树
        printTree(head.left,height + 1,"^",len);
    }

    /**
     * 获取指定空格
     * @param len
     * @return
     */
    private static String getSpace(int len){
        StringBuffer str = new StringBuffer();
        for(int i = 0; i < len; i++) {
            str.append(" ");
        }
        return str.toString();
    }

    
}
